package main.java.com.amanda.suafa;


import edu.princeton.cs.algs4.StdOut;
import main.java.com.amanda.innovate.DepthFirstOrder;
import main.java.com.amanda.innovate.DirectedCycle;
import main.java.com.amanda.innovate.EdgeWeightedDirectedCycle;
import main.java.com.amanda.utils.Digraph;
import main.java.com.amanda.utils.EdgeWeightedDigraph;

/**
 * @author amanda
 * @Description 算法4.5 拓扑排序
 */
public class Topological {
    private Iterable<Integer> order;    // 顶点的拓扑排序
    private int[] rank;

    public Topological(EdgeWeightedDigraph G) {
        EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }
    public Topological(Digraph G) {
        DirectedCycle finder = new DirectedCycle(G);
        if (!finder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
            rank = new int[G.V()];
            int i = 0;
            for (int v : order)
                rank[v] = i++;
        }
    }


    public Iterable<Integer> order() {
        return order;
    }
    public boolean isDAG() {
        return order != null;
    }
}
